package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.ArrayList;
import java.util.List;

/**
 * 实给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * <p>
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * <p>
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * <p>
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * <p>
 * 说明:
 * <p>
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于 maxWidth。
 * 输入单词数组 words 至少包含一个单词。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/text-justification
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0068 extends Printer {

    public static void main(String[] args) {
        Solution_0068 solution = new Solution_0068();
//        List<String> s = solution.fullJustify(new String[]{"What","must","be","acknowledgment","shall","be"}, 16);
        List<String> s = solution.fullJustify(new String[]{"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"},
                20);
        print(s);
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<>();
        int n = words.length, i = 0, j = 0, blank = 0, rest, wdCnt;
        while (i < n) {
            rest = maxWidth;
            wdCnt = 0;
            blank = 0;
            while (j < n && rest >= words[j].length()) {
                rest -= words[j++].length();
                wdCnt++;
                //如果后面还要接单词，至少要留一个空格
                rest -= 1;
                blank++;
            }
            blank += rest;
            StringBuilder sb = new StringBuilder();
            //特殊情况1， 如果是最后一行， 单词之间只占一个空格
            if (j >= n) {
                while (i < j) {
                    sb.append(words[i++]).append(" ");
                }
                sb.deleteCharAt(sb.length() - 1);
                while (sb.length() < maxWidth) {
                    sb.append(" ");
                }
            } else if (wdCnt == 1) {
                //特殊情况2， 如果一行只有一个单词， 补齐右边的空格
                while (i < j) {
                    sb.append(words[i++]).append(" ");
                }
                sb.deleteCharAt(sb.length() - 1);
                while (sb.length() < maxWidth) {
                    sb.append(" ");
                }
            } else {
                //普通情况
                int mod = blank % (wdCnt - 1);
                int bsn = blank / (wdCnt - 1);
                while (i < j) {
                    sb.append(words[i++]);
                    int k = bsn + (mod > 0 ? 1 : 0);
                    mod--;
                    if (i < j) {
                        for (int l = 0; l < k; l++) {
                            sb.append(" ");
                        }
                    }
                }
            }
            i = j;
            list.add(sb.toString());
        }
        return list;
    }
}
